package com.wbt.tenxun;

public class Main {

    public static void main(String[] args) {
        int[] pre = {3,9,20,15,7};
        int[] ino = {9,3,15,20,7};

        Node tree = getTree(pre,ino);

        printTree(tree);
    }


    public static Node getTree(int[] pre,int[] ino){

        int root = pre[0];
        int length = pre.length;
        Node tree = new Node(root);
        tree.l = tree.r = null;

        if (pre.length == 1){
            return tree;
        }

        int index = 0;
        while (ino[index] != root){
            index ++ ;
        }
        if(index > 0){
            int[] leftPer = new int[index];
            for(int i=0; i <leftPer.length ;i++){
                leftPer[i] = pre[i+1];
            }
            int[] leftIno = new int[index];
            for(int i=0; i <leftIno.length ;i++){
                leftIno[i] = ino[i];
            }
            tree.l = getTree(leftPer,leftIno);
        }

        int rightLength = length - index -1;
        if(rightLength > 0){
            int[] rightPer = new int[rightLength];
            for(int i=0; i <rightPer.length ;i++){
                rightPer[i] = pre[i+ index +1];
            }
            int[] rightIno = new int[rightLength];
            for(int i=0; i <rightIno.length ;i++){
                rightIno[i] = ino[i+ index + 1];
            }
            tree.r = getTree(rightPer,rightIno);
        }

        return tree;
    }

    public static void printTree(Node node){

        int treeDepth = getTreeDepth(node);

        int arrayHeight = treeDepth * 2 - 1;
        int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;

        String[][] res = new String[arrayHeight][arrayWidth];
        for (int i = 0; i < arrayHeight; i ++) {
            for (int j = 0; j < arrayWidth; j ++) {
                res[i][j] = " ";
            }
        }
        writeArray(node, 0, arrayWidth/ 2, res, treeDepth);

        for (String[] line: res) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < line.length; i ++) {
                sb.append(line[i]);
                if (line[i].length() > 1 && i <= line.length - 1) {
                    i += line[i].length() > 4 ? 2: line[i].length() - 1;
                }
            }
            System.out.println(sb.toString());
        }
    }
    private static void writeArray(Node currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {

        if (currNode == null) return;
        res[rowIndex][columnIndex] = String.valueOf(currNode.val);

        int currLevel = ((rowIndex + 1) / 2);
        if (currLevel == treeDepth) return;
        int gap = treeDepth - currLevel - 1;

        if (currNode.l != null) {
            res[rowIndex + 1][columnIndex - gap] = "/";
            writeArray(currNode.l, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
        }

        if (currNode.r != null) {
            res[rowIndex + 1][columnIndex + gap] = "\\";
            writeArray(currNode.r, rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
        }
    }
    public static int getTreeDepth(Node root) {
        return root == null ? 0 : (1 + Math.max(getTreeDepth(root.l), getTreeDepth(root.r)));
    }
}

  class Node{
    int val ;
    Node l;
    Node r;

    public Node(int val){
        this.val = val;
    }
  }
